package tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName InvertTree
 * @Date 2024/10/15 10:21 28
 * @Author Jack Chen
 * @Description 反转二叉树，并返回根节点，输入root = [4,2,7,1,3,6,9] 输出[4,7,2,9,6,3,1],节点树在[0,100],-100<=Node.val<=100
 * @Version 1.0
 */

public class InvertTree {

    public static List<Integer> list1 = new ArrayList<>();
    public static List<Integer> list2 = new ArrayList<>();

    public static void main(String[] args) {
        // 初始化节点
        TreeNode node1 = new TreeNode(4);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(7);
        TreeNode node4 = new TreeNode(1);
        TreeNode node5 = new TreeNode(3);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(9);
        // 构建节点之间的引用（指针）
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;

        // 获取结构化的list
        List<List<Integer>> nestedList = levelOrderBottom(node1);
        // 使用嵌套for循环遍历并输出所有元素
        for (List<Integer> innerList : nestedList) {
            for (Integer number : innerList) {
                System.out.print(number + " ");
            }
            System.out.println(); // 每一行内部列表后换行
        }

        inOrder(node1);
        list1.forEach(System.out::println);

        invertTree(node1);   // 反转二叉树

        System.out.println("after invert tree");

        inOrder(node1);
        list2.forEach(System.out::println);
    }

    // 从下往上输出每层的元素值
    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        if(root == null)
            return result;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            List<Integer> subList = new LinkedList<Integer>();
            int levelSize = queue.size();    //记录每层的元素个数，每层建立一个subList
            for(int i = 0; i < levelSize; i++) {    //按层循环，循环次数为每层的元素个数
                TreeNode node = queue.poll();    //访问完后从队列删除，保证queue.size()等于每层的元素个数
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
                subList.add(node.val);
            }
            result.add(0,subList);    //第一个参数为index，从链表头插入
        }
        return result;
    }

    public static void preOrder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }
        // 访问优先级：根节点 -> 左子树 -> 右子树
        list.add(root.val);
        preOrder(root.left, list);
        preOrder(root.right, list);
    }

    public static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 访问优先级：左子树 -> 根节点 -> 右子树
        inOrder(root.left);
        list1.add(root.val);
        inOrder(root.right);
    }

    public static TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        // 先递归
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        // 最后再交换
        root.left = right;
        root.right = left;
        return root;
    }
}